home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 18333 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.6 KB

  1. Path: ix.netcom.com!news
  2. From: Bradd W. Szonye <bradds@ix.netcom.com>
  3. Newsgroups: comp.lang.c++
  4. Subject: RE: Fastest Sorting Algorithm?
  5. Date: 19 Apr 1996 09:45:44 GMT
  6. Organization: Netcom
  7. Message-ID: <01bb2dd5.45612920$c6c2b7c7@Zany.localhost>
  8. References: <Dou55w.7MB@novice.uwaterloo.ca> <DpAxtI.3w9@undergrad.math.uwaterloo.ca> <4k15rt$nbb@news.microsoft.com>
  9. NNTP-Posting-Host: det-mi6-06.ix.netcom.com
  10. X-NETCOM-Date: Fri Apr 19  4:45:44 AM CDT 1996
  11. X-Newsreader: Microsoft Internet News
  12.  
  13.  
  14. On Thursday, April 04, 1996, Dann Corbit wrote...
  15. > In article <DpAxtI.3w9@undergrad.math.uwaterloo.ca>,
  16. sckettle@undergrad.math.uwaterloo.ca says...
  17. > >
  18. > >In article <Dou55w.7MB@novice.uwaterloo.ca>,
  19. > >Gerald Wang  <GTWANG@HELIX.Watstar.UWaterloo.CA> wrote:
  20. > >>A classmate was recently asked during a job interview what is the
  21. fastest 
  22. > >>method to sort an array of numbers. He replied "Use a quicksort." They
  23.  
  24. > >>asked "And how would you make it faster still?" He couldn't come up
  25. with 
  26. > >>much...end of interview.
  27. > >>
  28. > >>I know it's a vague question... Any ideas on what they were asking? Or
  29.  
  30. > >>what the right answer is?
  31. > >>
  32. > >>Gerald
  33. > >>
  34. >
  35. >>------------------------------------------------------------------------
  36. -
  37. > >>Gerald Wang
  38. > >>http://www.csclub.uwaterloo.ca/~gtwang
  39. > >>
  40. > >>
  41. > >
  42. > >Well you could use a type of bucket sorting algorithm which is faster
  43. than
  44. > >quicksort when sorting integers.  How to make it faster I don't know -
  45. you
  46. > >don't really make algortithms faster you make code implementations of
  47. > >algorithms faster. Mybe they meant tweaking stratigies for quicksort
  48. like how
  49. > >to choose a pivot element.  Who knows. 
  50. > Bucket sort, counting sort and radix sort are all faster if there are a 
  51. > large number of elements.
  52. > Their question about how to make it faster still was probably to see how
  53. > he tackles problems.  They may have wanted something like:
  54. > 1.  Research avalable sorting algorithms
  55. > 2.  Select best algorithm for problem space
  56. > 3.  Profile the chosen implementation to find bottlenecks
  57. > 4.  Optimize the small fraction of code that is the greatest bottleneck.
  58. > Alternatives:
  59. > 1.  Buy a sorting package
  60. > 2.  Use a database to do the sorting
  61. > -- 
  62. > The opinions expressed in this message are my own personal views
  63. > and do not reflect the official views of Microsoft Corporation.
  64. > In fact, I'm just a subcontractor, not an employee, so pull in your
  65. claws.
  66.  
  67. The fastest sort depends on what you're trying to do.
  68.  
  69. For large, arbitrary, badly-distributed, memory-based data, Quicksort is
  70. great.
  71. For disk-based data, Mergesort is great.
  72. For well-distributed binary data, radix sort is great.
  73. For small data sets, insertion sort is great.
  74.  
  75.  
  76.